package BF_DP;

public class Test5 {
    /*
    求方法数:
    * arr 里面都是正数, 没有重复值,每一个值代表一种货币,每一种都可以用无数张
    * 最用要找的零钱数是aim
    * 找零的方法数返回*/
    public static int way1(int[] arr,int aim){
        return process(arr,0,aim);
    }
    public static int process(int[] arr,int index ,int rest){
        if(index == arr.length){
            //如果没有钱数可以选了,有一种特殊情况就是需要钱了
            return rest == 0?1:0;
        }
        //arr[index]0...rest去尝试但是不超过rest的钱数
        int ways =0;
        for (int zhang = 0; arr[index] * zhang <= rest ; zhang++) {
            ways +=process(arr,index+1,rest-arr[index]*zhang);
        }
        return ways;
    }
    //改动态规划 - 但出现某种枚举行为怎么改
    public static int way2(int[] arr,int aim){
        /*时间复杂度 O(N * aim^2)*/
        if (arr == null || arr.length ==0){
            return 0;
        }
        //最终位置也要
        int[][] dp = new int[arr.length+1][aim+1];
        dp[arr.length][0] =1;
        for (int index = arr.length-1; index >=0 ; index--) {
            for (int rest = 0; rest <= aim ; rest++) {
                int ways =0;
                for (int zhang = 0; arr[index] * zhang <= rest ; zhang++) {
                    ways +=dp[index+1][rest-arr[index]*zhang];
                }
                dp[index][rest] =ways;
                
            }
        }
        return dp[0][aim];
    }
    public static int way3(int[] arr,int aim){
        /*时间复杂度 O(N * aim^2)*/
        if (arr == null || arr.length ==0){
            return 0;
        }
        //最终位置也要
        int[][] dp = new int[arr.length+1][aim+1];
        dp[arr.length][0] =1;
        for (int index = arr.length-1; index >=0 ; index--) {
            for (int rest = 0; rest <= aim ; rest++) {

                /*当前格子,总是需要下方的格子,和自己本行减去一个面值的格子*/
                dp[index][rest] = dp[index+1][rest]+rest;
                if (rest - arr[index] >=0){//别越界就能加
                    dp[index][rest] += dp[index][rest-arr[index]];
                }
            }
        }
        return dp[0][aim];
    }
}
